{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Finding the Number of Visible Mountains"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #sorting #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #排序 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: visibleMountains"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #寻找可见山的数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个 <strong>下标从 0 开始&nbsp;</strong>的二维整数数组 <code>peaks</code>，其中 <code>peaks[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> 表示山 <code>i</code> 在坐标 <code>(x<sub>i</sub>, y<sub>i</sub>)</code>&nbsp;处有一个峰值。山可以被描述为一个直角等腰三角形，它的底部沿着 <code>x</code>&nbsp;轴，山峰处有一个直角。更正式地说，上山和下山的&nbsp;<strong>梯度&nbsp;</strong>分别为 <code>1</code>&nbsp;和 <code>-1</code>。</p>\n",
    "\n",
    "<p>一座山如果它的顶峰不在另一座山 (包括其他山的边界) 之内，那么它被认为是&nbsp;<strong>可见&nbsp;</strong>的。</p>\n",
    "\n",
    "<p data-group=\"1-1\">返回<em>可见山的数量。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/07/19/ex1.png\" style=\"width: 402px; height: 210px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> peaks = [[2,2],[6,3],[5,4]]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong> 上面的图表显示了山脉。\n",
    "- 山 0 是可见的，因为它的峰值不在另一座山的里面或另一座山的边界。\n",
    "- 山 1 是不可见的，因为它的顶峰在山 2 的边界。\n",
    "- 山 2 是可见的，因为它的峰值不在另一座山的里面或另一座山的边界。\n",
    "有 2 座山是可见的。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/07/19/ex2new1.png\" style=\"width: 300px; height: 180px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> peaks = [[1,3],[1,3]]\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:</strong> 上面的图表显示了这些山 (它们完全重叠)。\n",
    "两座山都看不见，因为它们的山峰在彼此里面。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= peaks.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>peaks[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [finding-the-number-of-visible-mountains](https://leetcode.cn/problems/finding-the-number-of-visible-mountains/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [finding-the-number-of-visible-mountains](https://leetcode.cn/problems/finding-the-number-of-visible-mountains/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,2],[6,3],[5,4]]', '[[1,3],[1,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visibleMountains(self, peaks: List[List[int]]) -> int:\n",
    "        peaks.sort(key=lambda x:(x[0],-x[1]))\n",
    "        stark, last = [[-100000,1,0]], 0\n",
    "        for i,j in peaks:\n",
    "            if i != last:\n",
    "                while j - i >= stark[-1][1] - stark[-1][0]: stark.pop()\n",
    "                if stark[-1][1]+stark[-1][0] < i + j: stark.append([i,j,1])\n",
    "                last = i\n",
    "            elif stark[-1][1] == j: stark[-1][2] = 0\n",
    "        return sum(k for i,j,k in stark)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visibleMountains(self, peaks: List[List[int]]) -> int:\n",
    "        peaks.sort(key=lambda x:(x[0],-x[1]))\n",
    "        lastlocate,lasthigh=0,0\n",
    "        n=len(peaks)\n",
    "        mark=[[False for _ in range(2)]for _ in range(n)]\n",
    "        for i,(a,b) in enumerate(peaks):\n",
    "            if lasthigh-a+lastlocate>=b:\n",
    "                continue\n",
    "            mark[i][0]=True\n",
    "            lasthigh,lastlocate=b,a\n",
    "        \n",
    "        #peaks.sort(key=lambda x:(-x[0],-x[1]))\n",
    "        lastlocate,lasthigh=float(\"inf\"),0\n",
    "        n=len(peaks)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            a,b=peaks[i]\n",
    "            if lasthigh-lastlocate+a>=b:\n",
    "                continue\n",
    "            mark[i][1]=True\n",
    "            lasthigh,lastlocate=b,a\n",
    "        c=0\n",
    "        print(mark)\n",
    "        for i in range(n):\n",
    "            if mark[i][0] and mark[i][1]:\n",
    "                c+=1\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visibleMountains(self, peaks: List[List[int]]) -> int:\n",
    "        points = [(x - y, x + y) for x, y in peaks]\n",
    "        points.sort(key=lambda x: x[0])\n",
    "        groups = [list(group) for _, group in groupby(points, key=lambda x: x[0])]\n",
    "\n",
    "        res, maxY = 0, -int(1e20)\n",
    "        for group in groups:\n",
    "            cur = 0\n",
    "            for _, py in group:\n",
    "                if py > maxY:\n",
    "                    maxY = py\n",
    "                    cur = 1\n",
    "                elif py == maxY:  # 边界\n",
    "                    cur = 0\n",
    "            res += cur\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visibleMountains(self, peaks: List[List[int]]) -> int:\n",
    "\n",
    "        line=[]\n",
    "        for p in peaks:\n",
    "            line.append([p[0]-p[1],p[0]+p[1]])\n",
    "\n",
    "        line=sorted(line,key=lambda x:(x[0],-x[1]))\n",
    "        result=[]\n",
    "        used=[]\n",
    "        for node in line:\n",
    "            if not result:\n",
    "                result.append(node)\n",
    "            else:\n",
    "                while result:\n",
    "                    s_node=result[-1]\n",
    "                    if node[0]>=s_node[1]:\n",
    "                        result.append(node)\n",
    "                        break\n",
    "                    else:\n",
    "                        if node[1]<s_node[1]:\n",
    "                            break\n",
    "                        elif node[1]>s_node[1]:\n",
    "                            result.append(node)\n",
    "                            break\n",
    "                        else:\n",
    "                            if node[0]==s_node[0]:\n",
    "                                used.append(node)\n",
    "                                break\n",
    "                            else:\n",
    "                                break\n",
    "                \n",
    "        return len([i for i in result if i not in used ])\n",
    "                \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visibleMountains(self, peaks: List[List[int]]) -> int:\n",
    "\n",
    "        line=[]\n",
    "        for p in peaks:\n",
    "            line.append([p[0]-p[1],p[0]+p[1]])\n",
    "\n",
    "        line=sorted(line,key=lambda x:(x[0],-x[1]))\n",
    "        num=0\n",
    "        used=set([])\n",
    "        for idt in range(len(line)):\n",
    "            if idt in used:\n",
    "                continue\n",
    "            used.add(idt)\n",
    "            node_left=line[idt][0]\n",
    "            node_right=line[idt][1]\n",
    "            sign=1\n",
    "            for j in range(idt+1,len(line)):\n",
    "                new_node=line[j]\n",
    "                if new_node[0]>=node_right:\n",
    "                    break\n",
    "                else:\n",
    "                    if new_node[1]>node_right:\n",
    "                        continue\n",
    "                    elif new_node[1]<node_right:\n",
    "                        used.add(j)\n",
    "                    else:\n",
    "                        if new_node[0]==node_left:\n",
    "                            sign=0\n",
    "                        used.add(j)\n",
    "            num+=sign\n",
    "        return num\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visibleMountains(self, peaks: List[List[int]]) -> int:\n",
    "        res = []\n",
    "        for a, b in peaks:\n",
    "            res.append([a - b, a + b])\n",
    "        res.sort(key=lambda p: [p[0], -p[1]])\n",
    "        dq = deque([res[0]])\n",
    "        vis = set()\n",
    "        vis.add(tuple(res[0]))\n",
    "        for x, y in res[1:]:\n",
    "            while dq and dq[0][1] <= x:\n",
    "                dq.popleft()\n",
    "            if dq and dq[-1][1] >= y:\n",
    "                if (x, y) in vis:\n",
    "                    vis.remove((x, y))\n",
    "            else:\n",
    "                vis.add((x, y))\n",
    "                dq.append([x, y])\n",
    "        return len(vis)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visibleMountains(self, peaks: List[List[int]]) -> int:\n",
    "        interval_cnt = defaultdict(int) # 保存数量\n",
    "        interval_set = set() # 保存不重复山顶\n",
    "        for peak in peaks:\n",
    "            x,y = peak[0]-peak[1],peak[0]+peak[1]\n",
    "            interval_cnt[(x,y)] += 1\n",
    "            interval_set.add((x,y))\n",
    "        interval_set = list(interval_set)\n",
    "        interval_set.sort(key=lambda x:(x[0],-x[1]))\n",
    "        maxright = 0\n",
    "        ans = 0\n",
    "        for x,y in interval_set:\n",
    "            if y <= maxright: # 在该条件下也可能有重复的目标\n",
    "                continue\n",
    "            if interval_cnt[(x,y)] == 1:\n",
    "                ans += 1\n",
    "            maxright = y\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visibleMountains(self, peaks: List[List[int]]) -> int:\n",
    "        interval_cnt = defaultdict(int) # 保存数量\n",
    "        interval_set = set() # 保存不重复山顶\n",
    "        for peak in peaks:\n",
    "            x,y = peak[0]-peak[1],peak[0]+peak[1]\n",
    "            interval_cnt[(x,y)] += 1\n",
    "            interval_set.add((x,y))\n",
    "        interval_set = list(interval_set)\n",
    "        interval_set.sort(key=lambda x:(x[0],-x[1]))\n",
    "        maxright = 0\n",
    "        ans = 0\n",
    "        for x,y in interval_set:\n",
    "            if y <= maxright:\n",
    "                continue\n",
    "            if interval_cnt[(x,y)] == 1:\n",
    "                ans += 1\n",
    "            maxright = y\n",
    "            \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 区间转化 + 二维偏序\n",
    "    # 由于其山形均为等腰直角三角形,因此对于每一个顶点,我们可以将其转化为一个区间,一个山被挡住的前提是这个山代表的区间被另一个区间包含,因此我们按照区间的左端点升序排列,同时右端点降序排列之后,遍历数组并维护其最大的右端点即可;同时我们还需排除掉有相同区间的所有山顶 时间复杂度O(nlogn)\n",
    "    def visibleMountains(self, peaks: List[List[int]]) -> int:\n",
    "        # 映射为区间\n",
    "        cnt = collections.defaultdict(int)\n",
    "        ran = set()\n",
    "        for x,y in peaks:\n",
    "            ran.add((x - y, x + y))\n",
    "            cnt[(x - y, x + y)] += 1\n",
    "\n",
    "        ran = list(ran)\n",
    "        ran.sort(key = lambda x:(x[0], -x[1]))\n",
    "        ans = 0\n",
    "        maxr = 0\n",
    "        for x, y in ran:\n",
    "            if y <= maxr:\n",
    "                continue\n",
    "\n",
    "            maxr = max(maxr, y)\n",
    "\n",
    "            if cnt[(x, y)] == 1:\n",
    "                ans += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 区间转化 + 二维偏序\n",
    "    # 由于其山形均为等腰直角三角形,因此对于每一个顶点,我们可以将其转化为一个区间,一个山被挡住的前提是这个山代表的区间被另一个区间包含,因此我们按照区间的左端点升序排列,同时右端点降序排列之后,遍历数组并维护其最大的右端点即可;同时我们还需排除掉有相同区间的所有山顶 时间复杂度O(nlogn)\n",
    "    def visibleMountains(self, peaks: List[List[int]]) -> int:\n",
    "        # 映射为区间\n",
    "        cnt = collections.defaultdict(int)\n",
    "        ran = set()\n",
    "        for x,y in peaks:\n",
    "            ran.add((x - y, x + y))\n",
    "            cnt[(x - y, x + y)] += 1\n",
    "\n",
    "        ran = list(ran)\n",
    "        ran.sort(key = lambda x:(x[0], -x[1]))\n",
    "        ans = 0\n",
    "        maxr = 0\n",
    "        for x, y in ran:\n",
    "            if y <= maxr:\n",
    "                continue\n",
    "\n",
    "            maxr = max(maxr, y)\n",
    "\n",
    "            # 如果cnt[(x, y)] > 1 即多个重叠 都不算在内\n",
    "            if cnt[(x, y)] == 1:\n",
    "                ans += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visibleMountains(self, peaks: List[List[int]]) -> int:\n",
    "        # 映射为区间\n",
    "        cnt = collections.defaultdict(int)\n",
    "        ran = set()\n",
    "        for x,y in peaks:\n",
    "            ran.add((x - y,x + y))\n",
    "            cnt[(x - y,x + y)] += 1\n",
    "\n",
    "        ran = list(ran)\n",
    "        ran.sort(key = lambda x:(x[0],-x[1]))\n",
    "        ans = 0\n",
    "        maxr = 0\n",
    "        for x,y in ran:\n",
    "            if y <= maxr:\n",
    "                continue\n",
    "\n",
    "            if cnt[(x,y)] > 1:\n",
    "                maxr = max(maxr,y)\n",
    "            else:\n",
    "                maxr = max(maxr,y)\n",
    "                ans += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 区间转化 + 二维偏序\n",
    "    # 由于其山形均为等腰直角三角形,因此对于每一个顶点,我们可以将其转化为一个区间,一个山被挡住的前提是这个山代表的区间被另一个区间包含,因此我们按照区间的左端点升序排列,同时右端点降序排列之后,遍历数组并维护其最大的右端点即可;同时我们还需排除掉有相同区间的所有山顶 时间复杂度O(nlogn)\n",
    "    def visibleMountains(self, peaks: List[List[int]]) -> int:\n",
    "        # 映射为区间\n",
    "        cnt = collections.defaultdict(int)\n",
    "        ran = set()\n",
    "        for x,y in peaks:\n",
    "            ran.add((x - y, x + y))\n",
    "            cnt[(x - y, x + y)] += 1\n",
    "\n",
    "        ran = list(ran)\n",
    "        ran.sort(key = lambda x:(x[0], -x[1]))\n",
    "        ans = 0\n",
    "        maxr = 0\n",
    "        for x,y in ran:\n",
    "            if y <= maxr:\n",
    "                continue\n",
    "\n",
    "            if cnt[(x, y)] > 1:\n",
    "                maxr = max(maxr, y)\n",
    "            else:\n",
    "                maxr = max(maxr, y)\n",
    "                ans += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visibleMountains(self, peaks: List[List[int]]) -> int:\n",
    "        cnt = collections.defaultdict(int)\n",
    "        ran = set()\n",
    "        for x,y in peaks:\n",
    "            ran.add((x - y,x + y))\n",
    "            cnt[(x - y,x + y)] += 1\n",
    "\n",
    "        ran = list(ran)\n",
    "        ran.sort(key = lambda x:(x[0],-x[1]))\n",
    "        ans = 0\n",
    "        maxr = 0\n",
    "        for x,y in ran:\n",
    "            if y <= maxr:\n",
    "                continue\n",
    "            if cnt[(x,y)] > 1:\n",
    "                maxr = max(maxr,y)\n",
    "            else:\n",
    "                maxr = max(maxr,y)\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visibleMountains(self, peaks: List[List[int]]) -> int:\n",
    "        # 映射为区间\n",
    "        cnt = collections.defaultdict(int)\n",
    "        ran = set()\n",
    "        for x,y in peaks:\n",
    "            ran.add((x - y,x + y))\n",
    "            cnt[(x - y,x + y)] += 1\n",
    "\n",
    "        ran = list(ran)\n",
    "        ran.sort(key = lambda x:(x[0],-x[1]))\n",
    "        ans = 0\n",
    "        maxr = 0\n",
    "        for x,y in ran:\n",
    "            if y <= maxr:\n",
    "                continue\n",
    "            if cnt[(x,y)] > 1:\n",
    "                maxr = max(maxr,y)\n",
    "            else:\n",
    "                maxr = max(maxr,y)\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict, deque\n",
    "from functools import cache, lru_cache\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def visibleMountains(self, peaks: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        :param peaks:\n",
    "        :return:\n",
    "        \"\"\"\n",
    " \n",
    "        cnt = defaultdict(int)\n",
    "        ran = set()\n",
    "        for x, y in peaks:\n",
    "            ran.add((x - y, x + y))\n",
    "            cnt[(x - y, x + y)] += 1\n",
    "\n",
    "        ran = list(ran)\n",
    "        ran.sort(key=lambda x: (x[0], -x[1]))\n",
    "        ans = 0\n",
    "        so_far = 0\n",
    "        for i in ran:\n",
    "            if i[1] <= so_far:\n",
    "                continue\n",
    "            else:\n",
    "                if cnt[i] > 1:\n",
    "                    so_far = max(so_far, i[1])\n",
    "                else:\n",
    "                    ans += 1\n",
    "                    so_far = max(so_far, i[1])\n",
    "        return ans\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
